#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <numeric>
using namespace std;

class Solution
{
public:
    int deleteAndEarn(vector<int> &nums)
    {
        map<int, int> M;

        vector<int> temp;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (M.find(nums[i]) == M.end())
            {
                temp.push_back(nums[i]);
            }
            M[nums[i]] += nums[i];
        }
        sort(temp.begin(), temp.end());
        //还是要走一遍动态规划
        vector<int> dp(temp.size(), 0);
        dp[0] = M[temp[0]];
        for (int i = 1; i < temp.size(); ++i)
        {
            int j = i - 1;
            int index = 0;
            while (1)
            {
                if (temp[j] + 1 < temp[i])
                {
                    dp[i] = max(dp[i], dp[j]);
                    index++;
                    j--;
                }
                else
                {
                    j = j - 1;
                }
                if (index >= 2||j<0)
                {
                    break;
                }
            }

            dp[i] = dp[i] + M[temp[i]];
        }
        return *max_element(dp.begin(), dp.end());
    }
};

int main()
{
    Solution S;
    vector<int> nums = {1, 1, 1, 2, 4, 5, 5, 5, 6};
    cout << S.deleteAndEarn(nums) << endl;
}